package strings;

import org.junit.jupiter.api.Test;

import java.util.*;

public class ReplaceKey {
    StringBuffer strb = new StringBuffer();

    public boolean test(){
        return  1>2 && 2>3;
    }

    public static void main(String[] args) {
        int[] ints = {2,4,56,2,7,0};

        boolean b = true;
        assert ints.length == 4;
        assert b == true;
        Integer i = Integer.MAX_VALUE;
        System.out.println();
        String s = "dd";
        s = s+'c';
        String c1 = String.valueOf('a');
        char c = s.charAt(1);
        StringBuffer strb = new StringBuffer();
        strb.append("123");
        String s1 = strb.toString();
    }

    /**
     * 将AAABBCCCD压缩为A3B2C3A1D1
     * 使用快慢指针循环遍历
     */
    @Test
    void testString(){
        String str = "AAABBCCCD";
        char[] chars = str.toCharArray();
        StringBuffer stringBuffer = new StringBuffer();
        int l=0,r=1,n=str.length();
        stringBuffer.append(chars[0]);
        int count = 1;
        while (r<n){
            if (chars[l] != chars[r]){
                stringBuffer.append(count);
                stringBuffer.append(chars[r]);
                l = r;
                count = 1;
            }else if(chars[l] == chars[r]){
                count++;
            }
            r++;
            if (r == n){
                stringBuffer.append(count);
            }
        }
        System.out.println(stringBuffer);
    }





    @Test
    void yasuoString(){
        String str = "AAABBCCDF";
        char[] chars = str.toCharArray();
        StringBuffer stringBuffer = new StringBuffer();
        int slow = 0;
        int fast = 1;
        int count = 1;
        while (slow < str.length()-1){
            if (str.charAt(slow) == str.charAt(fast)){
                fast++;
                count++;
            }else {
                stringBuffer.append(str.charAt(slow));
                stringBuffer.append(count);
                count = 1;
                slow = fast;
                fast++;
            }
        }
        stringBuffer.append(str.charAt(slow));
        stringBuffer.append(count);
        String res = stringBuffer.toString();
        System.out.println(res);
    }

    /**
     * 给一个数组，获取第二大和倒数第二大的差值
     * 思路是先定义几个默认的值；最小值定义为Integer.MAX_VALUE;
     * 一次循环，获取到对应的值
     */

    @Test
    void getChaZhi(){

        int arr[] = {55, 10, 8, 90, 43, 87, 95, 25, 50, 12};
        quickSort(arr,0,arr.length-1);
        int firstMax = Integer.MIN_VALUE;
        int secondMax = Integer.MIN_VALUE;
        int firstMin = Integer.MAX_VALUE;
        int secondMin = Integer.MAX_VALUE;
        for(int num:arr){
            if(num>firstMax){
                secondMax = firstMax;
                firstMax = num;
            }else if(num<firstMax && num>secondMax){
                secondMax = num;
            }
            if(num<firstMin){
                secondMin = firstMin;
                firstMin = num;
            }else if(num>firstMin && num<secondMin){
                secondMin = num;
            }
        }
        int res = secondMax-secondMin;
        System.out.println(res);

    }


    /**
     * 快速排序，写代码一定要注意的事情：长度length的处理，如果是从右边还是的一定是--
     * {55, 10, 8, 90, 43, 87, 95, 25, 50, 12}
     * @param ints
     * @param left
     * @param right
     */
    public void quickSort(int[] ints,int left, int right){
        if (left<right){
            int l = left;
            int r = right;
            int temp = ints[l];
            while (l < r){
                while (l < r && temp < ints[r]){
                    r--;
                }
                if (l < r){
                    ints[l] = ints[r];
                    l++;
                }
                while (l < r && ints[l] < temp){
                    l++;
                }
                if (l < r){
                    ints[r] = ints[l];
                }
            }
            ints[l] = temp;
            quickSort(ints, left, l-1);
            quickSort(ints, l+1, right);

//            if (left < right){
//                int l=left, r=right;
//                int temp = ints[l];
//                while (l<r){
//                    while (l<r && temp < ints[r]){
//                        r--;
//                    }
//                    if (l<r){
//                        ints[l] = ints[r];
//                        l++;
//                    }
//                    while (l<r && temp > ints[l]){
//                        l++;
//                    }
//                    if (l<r){
//                        ints[r] = ints[l];
//                    }
//                }
//                ints[l] = temp;
//                quickSort(ints, left, l-1);
//                quickSort(ints, l+1, right);
//            }
        }
    }

    /**
     * 字符串找出最大公共字符，abcacae  -> abc；abbbbb
     * 快慢指针循环，
     */
    @Test
    void maxStr(){
        String string = "abcacae";
        int l=0,r=1;
        String res = "";
        while (r<string.length()){
            if (string.substring(l,r).indexOf(string.charAt(r)) < 0){
                r++;
            } else {
                if (res.length() < r-l){
                    res = string.substring(l,r);
                }
                l=r;
                r++;
            }
        }
        System.out.println(res);
    }




    @Test
    void getPublicString(){
        String s= "abbbbb";
        int slow = 0;
        int fast = 1;
        String res = "";
        String temp = "";
        while (fast < s.length()){
            if (s.substring(slow, fast).indexOf(s.charAt(fast)) < 0 ){
                fast++;
            }else {
                if (res.length() < s.substring(slow,fast).length()){
                    res = s.substring(slow,fast);
                }
                slow = fast;
                fast++;
            }
        }
        System.out.println(res);

    }

    public String gcdOfStrings(String str1, String str2) {
        LinkedList<Boolean> resList = new LinkedList<Boolean>();

        if(str1.length() == 0 || str2.length() == 0){
            return "";
        }
        if((str1+str2).equals(str2+str1)){
            int len1=str1.length();
            int len2=str2.length();
            while(len2!=0){
                int temp = len2;
                len2=len1%len2;
                len1=temp;

            }
            return str1.substring(0,len1-1);
        }else{
            return "";
        }
    }

    @Test
    void testgcd(){
        char[] res = new char[]{};

        String s = "a good   example";
        String[] strings = s.split(" ");
        List<String> stringList = new ArrayList<String>();
        for(int i=0; i<strings.length; i++){
            if(strings[i].length() != 0) {
                stringList.add(strings[i]);
            }
        }
        Collections.reverse(stringList);
        String res1 = String.join(" ",stringList);



        System.out.println();
        reverseVowels("leetcode");
        String s1= "aaaaafsr";
        int a = s.indexOf('a');
        String str1 = "ABCABCABC";
        String str2 = "ABC";
        String res2 = gcdOfStrings(str1,str2);
        LinkedHashMap<Integer,Character> map = new LinkedHashMap<Integer, Character>();

        Set<Integer> list = map.keySet();
        Collection<Character> l = map.values();
        StringBuffer strRes = new StringBuffer();
        List<Integer> lit = new ArrayList<Integer>();
        int i= 0;
        map.get(lit.get(lit.size()-i-1));
        lit.remove(0);


    }

    public String reverseVowels(String s) {
        // 先循环字符串，把元音提取出来。存到map里面。key是索引，value是对应的char
        // 再次循环，如果map里面containsKey能找到对应的索引。找到map里面对应的反索引；get出来补上
        // 5 4 2 5 6 0
        LinkedHashMap<Integer,Character> map = new LinkedHashMap<Integer, Character>();
        char c = 'p';

        String strY = "aeiouAEIOU";
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0; i<s.length(); i++){
            if(strY.indexOf(s.charAt(i)) >= 0){
                map.put(i, s.charAt(i));
                list.add(i);
            }
        }
        Collections.reverse(list);
        int listIndex = 0;
        StringBuffer strRes = new StringBuffer();
        for(int i=0; i<s.length(); i++){
            if(list.contains(i)){
                strRes.append(map.get(list.get(listIndex)));
                listIndex++;
            }else{
                strRes.append(s.charAt(i));
            }
        }
        return strRes.toString();
    }

    @Test
    void compress() {
        // start和end指针，end指针从1开始
        //
        char chars[] = {'a','a','b','b','c','c','c'};

        int start = 1;
        int end = 2;
        int res_index = 1;
        int count = 1;
        char[] res = new char[chars.length];
        res[0] = chars[0];
//        if(chars.length == 1){
//            return res.length;
//        }
        for(int i=1; i<chars.length; i++){
            if(chars[start] == chars[end]){
                count++;
            }
            if(chars[start] != chars[end]){
                if(count>1){
                    String s = String.valueOf(count);
                    for(int j=0; j<s.length(); j++){
                        res[res_index] = s.charAt(j);
                        res_index++;
                    }
                    res_index++;
                    res[res_index] = chars[end];
                }
                start = end;
            }
            if(end <= chars.length - 1){
                end++;
            }

        }
        System.out.println(res.length);
    }

    @Test
    public void moveZeroes() {
        double res1 = -1/1;
        System.out.println();
        double res = -Double.MIN_VALUE;
        int[] nums = {1,2,3,0,1};
        //双指针循环，当满指针非0，并且快指针为0，替换位置
        int n = nums.length;
        int left=0;
        for(int right=0; right<n; right++){
            if(nums[right] != 0 ){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }


        }
        System.out.println();

    }

    @Test
    public void findMaxAverage() {
        HashSet<Integer> set = new HashSet<>();
        ArrayList<Integer> list = new ArrayList<>();
        list.contains(1);
        int[] ints = new int[5];
        int[] nums = {-1};
        int k = 1;
        // 滑动窗口获取最大和，在计算最大平均数
        int n = nums.length;
        double max = -Double.MIN_VALUE;
        for(int i=0; i<=n-k; i++){
            double sum=0.0;
            int target = i;
            int k1=k;
            while(k1>0){
                sum=sum+nums[target];
                target++;
                k1--;
            }
            max = Math.max(max,sum);
        }
        double res = max/k;
    }

    /**
     * 翻转数字
     */

    @Test
    void reserve(){
        int n = 123;
        int m = 0;
        while (n > 0){
            int temp = n%10;
            n = n/10;
            m = m*10 + temp;
        }
        System.out.println(m);
    }








    @Test
    void tranInt(){
        int num = 213;
        int res = 0;
        int temp = 0;
        while (num/10 != 0){
            temp = num % 10;
            num = num/10;
            res = res*10 + temp;
        }
        res = res*10 + num;
        System.out.println(res);
    }

    @Test
    void testS(){
        String[] re = generatePermutation("abc");
        System.out.println();

    }

    Set<String> res=new HashSet<>();
    public String[] generatePermutation (String s) {
        //转化为字符数组
        char[] arr=s.toCharArray();
        //回溯
        dfs(arr,new StringBuilder(),0);
        return res.toArray(new String[res.size()]);
    }

    private void dfs(char[] arr,StringBuilder sb,int index){
        res.add(sb.toString());
        for(int i=index;i<arr.length;i++){
            //添加当前字符
            sb.append(arr[i]);
            //对下一位进行递归
            dfs(arr,sb,i+1);
            //回退到不添加的状态
            sb.deleteCharAt(sb.length()-1);
        }
    }

    @Test
    void merge() {
        int[] A={4,5,7};
        int m=3;
        int[] B={1,2,3};
        int n=3;
        int[] res = new int[m+n];
        int i=0; //A的下标指针
        int j=0; //B的下标指针
        int k=0;
        while(k<m+n && (i<m || j<n)){
            if(j<n && A[i] >= B[j]){
                res[k] = B[j];
                if(j<n){
                    j++;
                }
            }else{
                res[k] = A[i];
                if(i<m-1){
                    i++;
                }
            }
            k++;
        }
        System.out.println();

    }


    @Test
    void tst(){
        System.out.println("Hello World!");
        int[] intA = {4,5,6};
        int[] intB = {1,2,3};
        int n = intA.length; // intA
        int m = intB.length;
        int[] res = new int[m+n];
        int i=0; // intA
        int j=0; // intB
        int k=0;
        while(k<m+n && (i<n || j<m)){
            if(j<m || (i<n && intA[i] < intB[j] )){
                res[k] = intA[i];
                if(i<n){
                    i++;
                }
            }else{
                res[k] = intB[j];
                if(j<m-1){
                    j++;
                }
            }
            k++;
        }
        for(int ii : res){
            System.out.println(ii);
        }
    }







}
